import java.util.Stack;

public  class Sort {
    private static void swap(int[] a, int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }

    //三数取中
    private static int middleNum(int[] array,int left,int right) {
        int mid = (left+right)/2;
        if(array[left]<array[right]) {
            if(array[mid]<array[left]) {
                return left;
            }else if(array[mid]<array[right]) {
                return mid;
            }else {
                return right;
            }
        }else {
            if(array[mid]<array[right]) {
                return right;
            }else if(array[mid]<array[left]) {
                return mid;
            }else {
                return left;
            }
        }
    }

    private static int partSort1(int[] array, int left, int right) {
        int keyi = left;
        while (left < right) {
            while (left < right && array[right] >= array[keyi]) {
                right--;
            }
            while (left < right && array[left] <= array[keyi]) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, keyi, left);
        return left;
    }

    //挖坑法
    private static int partSort2(int[] array, int left, int right) {
        int hole = left;
        int key = array[left];
        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }
            array[hole] = array[right];
            hole = right;
            while (left < right && array[left] <= key) {
                left++;
            }
            array[hole] = array[left];
            hole = left;
        }
        array[hole] = key;
        return hole;
    }

    //前后指针法
    private static int partSort3(int[] array, int left, int right) {
        int prev = left,cur = left+1;
        int keyi = left;
        while(cur<=right) {
            if(array[cur]<array[keyi]) {
                prev++;
                if(prev!=cur) {
                    swap(array,prev,cur);
                }
            }
            cur++;
        }
        swap(array,keyi,prev);
        return prev;
    }

    public static void quickSort(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        if(end - begin +1 <= 15) {
            insertSort(array,begin,end);
            return;
        }
        int index = middleNum(array,begin,end);
        swap(array,index,begin);
        int keyi = partSort3(array, begin, end);
        quickSort(array, begin, keyi - 1);
        quickSort(array, keyi + 1, end);
    }

    public static void quickSortNonR(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        if(end - begin +1 <= 15) {
            insertSort(array,begin,end);
            return;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(end);
        stack.push(begin);
        while(!stack.isEmpty()) {
            int left = stack.pop();
            int right = stack.pop();
            int index = middleNum(array,left,right);
            swap(array,index,left);

            int keyi = partSort3(array, left, right);
            if(right>keyi+1) {
                stack.push(right);
                stack.push(keyi+1);
            }
            if(left<keyi-1) {
                stack.push(keyi-1);
                stack.push(left);
            }
        }
    }

    public static void insertSort(int[] array,int begin,int end) {
        for(int i=begin+1;i<=end;i++) {
            int tmp = array[i];
            int j = 0;
            for(j = i-1;j>=begin;j--) {
                if(array[j]>tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    public static void mergeSortFun(int[] array,int begin,int end) {
        if(begin>=end) {
            return;
        }
        int mid = (begin+end)/2;
        mergeSortFun(array,begin,mid);
        mergeSortFun(array,mid+1,end);

    }
}
